Giám mục Tân cử Kiều Công Tùng sinh ngày 24 tháng 8 năm 1964, tại Long Bình, Thủ Đức, Sài Gòn (nay là phường Long Bình, thành phố Thủ Đức, thành phố Hồ Chí Minh), thuộc Giáo xứ Cao Thái, Tổng giáo phận Sài Gòn.[3] Nguyên quán của ông thuộc giáo xứ Cao Mộc, xã Đồng Tiến, huyện Quỳnh Phụ, tỉnh Thái Bình, thuộc Giáo phận Thái Bình.[6][gc 1] Ngoài nguyên quán thân phụ là Cao Mộc, nguyên quán thân mẫu ông thuộc giáo xứ Lạc Thành, xã Tây Ninh, huyện Tiền Hải, tỉnh Thái Bình, thuộc Giáo phận Thái Bình.[cần dẫn nguồn] Song thân ông chỉ có hai người con trai, trong một dòng họ có nhiều tu sĩ: một người bác là linh mục (bên họ mẹ) và một bác là nữ tu (bên họ cha). Anh ông từng từng theo học tại Tiểu chủng viện Long Xuyên. Thân mẫu ông hiện đã 84 tuổi.[7]

Giai đoạn năm 1975, cậu bé Tùng sắp sửa thi vào Tiểu chủng viện Xuân Lộc. Vì thời cuộc, cậu bé Tùng không theo học chủng viện, và ý định đi tu một lần nữa trở lại vào độ tuổi Đại học, khi cậu đủ tuổi để ghi danh vào Đại chủng viện. Do ngại ngần và khó mở lời, chính người bác linh mục đã giúp cậu ngỏ lời với mẹ và giúp ghi danh vào Đại chủng viện Thánh Giuse Sài Gòn.[7] Kiều Công Tùng tốt nghiệp trường Đại học Nông Lâm Thành phố Hồ Chí Minh với văn bằng Kỹ sư Nông nghiệp.[2]

Khởi đầu việc tu học từ tháng 10 năm 1993 bằng việc gia nhập Đại chủng viện Thánh Giuse Sài Gòn, chủng sinh Phêrô Kiều Công Tùng tu học tại đây cho đến tháng 7 năm 1999.[3][8] Ông là chủng sinh khóa III của chủng viện này, cùng tu học với ba chủng sinh khác về sau trở thành giám mục là Louis Nguyễn Anh Tuấn, Giuse Đỗ Quang Khang và Giuse Bùi Công Trác. Đây là một việc rất đặc biệt khi có đến bốn giám mục xuất thân từ cùng một khóa Đại chủng viện.[9][10]